# -*- coding:utf-8 -*- 
__date__ = '2022/2/8 6:58 下午'

from util.list_util import random_list

# 分而治之 将两个已经排列好的序列合并成一个序列
def merge_sort(collection):
  length = len(collection)
  if length == 1:
    return collection
  left, right = collection[: length // 2], collection[length // 2:]
  return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
  result = []
  while left and right:
    if left[0] < right[0]:
      result.append(left.pop(0))
    else:
      result.append(right.pop(0))
  while left:
    result.append(left.pop(0))
  while right:
    result.append(right.pop(0))
  return result


if __name__ == '__main__':
  random_list = random_list(10)
  print('random_list: ', random_list)
  res = merge_sort(random_list)
  print(res, res == sorted(random_list))
